package com.xmg.dataStructure.tree.redblacktree;

import java.util.Scanner;

public class ExecRBTree {
    public static void main(String[] args) {
        BTree tree = new BTree();
        Scanner scanner = new Scanner(System.in);
        while (true){
            int val = scanner.nextInt();
            tree.add(val);
            TreeOperation.show(tree.getRoot());
        }
    }
}

class BTree{
    public static final boolean RED = true;
    public static final boolean BLACK = false;
    private Node root;

    public Node getRoot() {
        return root;
    }

    static class Node{
        int value;
        Node left;
        Node right;
        Node parent;
        boolean color;
        public Node(int value){
            this.value = value;
        }
    }

    public void rightRotate(Node x){
        Node y = x.left;
        x.left = y.right;
        if(y.right!=null){
            y.right.parent = x;
        }

        y.parent = x.parent;
        if(x.parent!=null){
            if(x==x.parent.left){
                x.parent.left = y;
            }else{
                x.parent.right = y;
            }
        }else{
            root=y;
        }

        y.right = x;
        x.parent = y;
    }

    public void leftRotate(Node x){
        Node y = x.right;
        x.right = y.left;
        if(y.left!=null){
            y.left.parent = x;
        }

        y.parent = x.parent;
        if(x.parent!=null){
            if(x==x.parent.left){
                x.parent.left = y;
            }else{
                x.parent.right = y;
            }
        }else{
            root=y;
        }

        y.left = x;
        x.parent = y;
    }

    public void add(int value){
        Node node = new Node(value);
        node.color = RED;
        Node parent = null;
        Node x = this.root;
        while (x!=null){
            parent = x;
            if(value<x.value){
                x = x.left;
            }else if(value > x.value){
                x = x.right;
            }else {
                return;
            }
        }
        node.parent = parent;
        if(parent==null){
            root = node;
        }else{
            if(value<parent.value){
                parent.left = node;
            }else{
                parent.right = node;
            }
        }
        infixup(node);
    }

    public void infixup(Node node){
        root.color = BLACK;
        Node parent = getParent(node);
        Node gparent = getParent(parent);

        //父节点为红色 且叔叔节点存在
        if (parent!=null && parent.color==RED){
            Node uncle = null;
            if(parent == gparent.left){
                uncle = gparent.right;
                if(uncle!=null && uncle.color==RED){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color = RED;
                    infixup(gparent);
                    return;
                }

                if(uncle==null || uncle.color==BLACK){
                    //ll
                    if(node==parent.left){
                        parent.color = BLACK;
                        gparent.color = RED;
                        rightRotate(gparent);
                    }else{
                        //lr
                        leftRotate(parent);
                        infixup(parent);
                    }
                }
            }else{
                uncle = gparent.left;
                if(uncle!=null && uncle.color==RED){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color = RED;
                    infixup(gparent);
                    return;
                }

                if(uncle==null || uncle.color==BLACK){
                    //RR
                    if(node==parent.right){
                        parent.color = BLACK;
                        gparent.color = RED;
                        leftRotate(gparent);
                    }else{
                        //RL
                        rightRotate(parent);
                        infixup(parent);
                    }
                }
            }
        }
    }

    public Node getParent(Node node){
        if(node == null){
            return null;
        }
        return node.parent;
    }
}
